3233. 统计不是特殊数字的数字数量

为保证权益，题目请参考 3233. 统计不是特殊数字的数字数量(From LeetCode).

解决方案1

说明

在这个题目中，由于特殊数字$n$的两个真因数中的一个必定是$1$，那么另一个在一定是$\mathrm{sqrt}(n)$。

这样，求解区间 $[l,r]$ 内不是特殊数字的数字数量就可以转换成了如何求解区间$[\mathrm{sqrt}(l),\mathrm{sqrt}r]$ 内是质数的数量的问题。

本题目的数据量不大，可以直接采用埃氏筛法来计算质数数量。

Python

from math import sqrt, floor, ceil


class Solution:
    def nonSpecialCount(self, l: int, r: int) -> int:

        nl = sqrt(l)
        nr = sqrt(r)

        prime_number = [True] * (floor(nr) + 1)
        for i in range(2, floor(nr) + 1):
            if prime_number[i]:
                for z in range(i * 2, int(nr) + 1, i):
                    prime_number[z] = False
            else:
                continue

        ans = 0
        for i in range(max(ceil(nl), 2), floor(nr) + 1):
            if prime_number[i]:
                ans += 1
        ans = (r - l + 1) - ans

        return ans